﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
// 原题连接：https://leetcode.cn/problems/valid-perfect-square/
/*
题目描述：
给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如  sqrt 。

示例 1：
输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

示例 2：
输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。
 

提示：
1 <= num <= 2^31 - 1
*/

// 方法1——枚举
/*
思路：
直接枚举1到num的所有数字，当出现i ^ 2 == num时，直接返回true，
当出现i ^ 2 > nums时，直接返回false。
虽说是枚举num个数，但实际最多只会枚举到sqrt(i)向上取整。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
bool isPerfectSquare1(int num) {
	long long i = 0; // i要用long long 防止溢出
	for (i = 1; i <= num; i++) {
		if ((i * i) > num) {
			return false;
		}
		else if ((i * i) == num) {
			return true;
		}
	}
	return false;
}
// 时间复杂度：O(sqrt(num))，我们最多只会枚举到sqrt(num)向上取整个数字。故时间复杂度为O(sqrt(num))。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法2——二分法
/*
思路：
其实我们完全可以用二分法来解决此题，起始时，我们让low等于1，high等于num
当mid ^ 2 < num时，说明此时的mid还较小，所以执行low = mid + 1
当mid ^ 2 > num时，说明此时的mid已经过大了，所以执行high = mid - 1
当mid ^ 2 == num时，直接返回true即可。
当low > high时，说明我们已经查找完了所有可能的区间依然找不到num的整数平方根，此时直接返回false即可。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
bool isPerfectSquare2(int num) {
	int low = 0;
	int high = num;
	int mid = 0;
	while (low <= high) {
		mid = low + (high - low) / 2;
		if ((mid ^ 2) < num) {
			low = mid + 1;
		}
		else if ((mid ^ 2) > num) {
			high = mid - 1;
		}
		else {
			return true;
		}
	}
	return false;
}
// 时间复杂度：O(logn)，n即为num。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

int main() {

	return 0;
}
